class Solution(object):
    def readBinaryWatch(self, turnedOn):
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        res = []  # 存储所有合法时间
        def backtrack(num, idx, hour, minute):
            """
            num: 当前已点亮的灯数
            idx: 当前考虑的灯编号（0~9）
            hour: 当前小时数
            minute: 当前分钟数
            """
            # 剪枝：小时不能超过11，分钟不能超过59
            if hour > 11 or minute > 59:
                return
            # 终止条件：点亮的灯数等于turnedOn
            if num == turnedOn:
                res.append(f"{hour}:{minute:02d}")
                return
            # 枚举下一个灯的位置
            for i in range(idx, 10):
                if i < 4:
                    # 前4个灯表示小时
                    backtrack(num + 1, i + 1, hour + (1 << i), minute)
                else:
                    # 后6个灯表示分钟
                    backtrack(num + 1, i + 1, hour, minute + (1 << (i - 4)))
        # 从第0个灯开始回溯
        backtrack(0, 0, 0, 0)
        return res 